package fun.coding.leetcode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class RestoreIpAddresses {

	public static void main(String[] args) {
		RestoreIpAddresses ins = new RestoreIpAddresses();
		List<String> test1 = ins.restoreIpAddresses("25525511135");
		LeetCodeHelpers.printGenericList(test1);
	}
	
	public List<String> restoreIpAddresses(String s) {
		List<String> finalRes = new LinkedList<String>();
		
		if (s == null || s.isEmpty()) return finalRes;
		if (s.length() < 4 || s.length() > 12) return finalRes;
		List<String> res = new LinkedList<String>();
		
		Set<String> set = new HashSet<String>();
		
		helper(s, 0, res, 0, set);
		
		finalRes.addAll(set);
		
		return finalRes;
    }

	// this is purely a recursion solution, could be optimized when using a lookup table for the strings that already processed
	private void helper(String s, int start, List<String> res, int count, Set<String> finalSet) {
		if (count == 3) {
			if (isValidSubIp(s.substring(start, s.length()))) {
				String tmp = res.get(0) + res.get(1) + res.get(2) + s.substring(start, s.length()); 
				finalSet.add(tmp);
			}
			return;
		}
		
		for (int i = start + 1; i <= start + 3 && i < s.length(); i++) {
			if (isValidSubIp(s.substring(start, i))) {
				res.add(s.substring(start, i) + ".");
				helper(s, i, res, ++count, finalSet);
				res.remove(res.size() - 1);
				count--;
			}
		}
	}
		
	private boolean isValidSubIp(String s) {
		//System.out.println(s);
		if (s == null || s.isEmpty()) return false;
		
		// prevent case like 00, 010, 01
		if (s.charAt(0) == '0') return s.equals("0");
		
		int v = Integer.parseInt(s);
		return v >= 0 && v < 256;
	}

}
